"""
NC52 有效括号序列

https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117&&tqId=37749&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return bool布尔型
#


class Solution:
    pairs = {
        "(": ")",
        "[": "]",
        "{": "}"
    }

    def method1(self, s: str) -> bool:
        """
        栈/队列：配对思路
        """
        size = len(s)
        # 长度不是偶数，直接返回False
        if size % 2:
            return False

        slst = list(s)
        tlst = []  # 临时变量，存放还没有配对的括号

        # 从左到右遍历字符串
        for tmp in slst:
            if len(tlst) > 0:
                # 获取最近的一个，待配对字符串
                # 如果当前获取的括号无法完成配对，则加入待配对括号队列
                # 配对成功，则清除配对完成的括号
                if self.pairs.get(tlst[-1], "") != tmp:
                    tlst.append(tmp)
                else:
                    tlst.pop()
            else:
                # 待配对队列为空，直接加入
                tlst.append(tmp)

        # 如果没有销完待配对的括号，则返回空值
        if len(tlst) > 0:
            return False

        return True

    def isValid(self, s: str) -> bool:
        # write code here
        assert len(s) > 0, "空字符串！！"

        return self.method1(s)


def test():
    obj = Solution()
    s = "[)])"
    # s = "(){}[]"
    res = obj.isValid(s)
    print(res)


if __name__ == "__main__":
    test()
